# -*- coding: utf-8 -*-
# @Time : 2023/9/13 15:30
# @Author  : lining
# @FileName: 图的深度优先遍历.py
"""
单纯遍历，没有应用到实际，存储方式为邻接表
edges = [[1,2],[1,3],[2,4],[3,5],[5,6],[4,6],[4,3],[3,2],[5,4]]
适合用递归做
栈---会先方便最右边的顶点
"""
class Dfs():
    def __init__(self, edges):
        # 边
        self.edges = edges
        # 各顶点是否已经访问过
        self.visited = {}
        # to边
        self.to_edges = {}
        # 访问结果
        self.visite_result = []

    def get_to_edges(self):
        for i in self.edges:
            # if i[0] not in self.visited:
            #     # 放到访问节点里
            #     self.visited[i[0]] = False
            # if i[1] not in self.visited:
            #     # 放到访问节点里
            #     self.visited[i[1]] = False
            # 没放在to边就新增这个key
            if i[0] not in self.to_edges:
                self.to_edges[i[0]] = [i[1]]
                continue
            # 已经在to边直接追加
            self.to_edges[i[0]].append(i[1])
        print(self.to_edges)

    def dfs(self, node):
        self.visite_result.append(node)
        # 放到已访问节点
        if node not in self.visited:
            self.visited[node] = True
        if node in self.to_edges:
            for i in self.to_edges[node]:
                if i not in self.visited:
                    self.visited[node] = True
                    self.dfs(i)


edges = [[1,2],[1,3],[2,4],[3,5],[5,6],[4,6],[4,3],[3,2],[5,4]]
a = Dfs(edges)
a.get_to_edges()
a.dfs(1)
print(a.visite_result)
